import collections
from typing import List


class Solution:
    def minDeletionSize(self, words: List[str]) -> int:
        stat = collections.defaultdict(set)
        size = len(words[0])

        # 标注所有不能共存的列
        for word in words:
            for i in range(size):
                for j in range(i + 1, size):
                    if word[i] > word[j]:
                        stat[i].add(j)

        # 定义状态矩阵
        dp = [1] * size

        # 状态转移
        for i in range(size - 2, -1, -1):
            for j in range(i + 1, size):
                if j not in stat[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        # 返回结果
        return size - max(dp)


if __name__ == "__main__":
    print(Solution().minDeletionSize(["babca", "bbazb"]))  # 3
    print(Solution().minDeletionSize(["edcba"]))  # 4
    print(Solution().minDeletionSize(["ghi", "def", "abc"]))  # 0
